/******************************************************************************
 *  A Teaching GA					  Developed by Hal Stringer & Annie Wu, UCF
 *  Version 2, January 18, 2004
 *******************************************************************************/

import java.io.*;
import java.util.*;

public class Search {

	/*******************************************************************************
	 * INSTANCE VARIABLES *
	 *******************************************************************************/

	/*******************************************************************************
	 * STATIC VARIABLES *
	 *******************************************************************************/

	public static int bestOfGenR;
	public static int bestOfGenG;
	public static int bestOfRunR;
	public static int bestOfRunG;
	public static int bestOverAllR;
	public static int bestOverAllG;

	public static double sumRawFitness;
	public static double sumRawFitness2; // sum of squares of fitness
	public static double sumSclFitness;
	public static double sumProFitness;
	public static double defaultBest;
	public static double defaultWorst;

	public static double averageBestRunFitness;
	public static double averageBestRunFitnessStd;
	public static double averageBestRunFitnessCi;
	public static double brfStdStorage[];

	public static int[] optimumGeneration;
	public static int sumOptimumGen;
	public static int sumOptimumGenSqr;
	public static double averageOptimumGenStd;
	public static double averageOptimumGenCi;

	public static double averageRawFitness;
	public static double stdevRawFitness;

	public static int G;
	public static int R;

	public static Random r = new Random();
	private static double randnum;

	private static int memberIndex[];
	private static double memberFitness[];
	private static int TmemberIndex;
	private static double TmemberFitness;

	private static double fitnessStats[][]; // 0=Avg, 1=Best

	/*******************************************************************************
	 * CONSTRUCTORS *
	 *******************************************************************************/

	/*******************************************************************************
	 * MEMBER METHODS *
	 *******************************************************************************/

	/*******************************************************************************
	 * STATIC METHODS *
	 *******************************************************************************/

	public static void main(String[] args) throws java.io.IOException {

		Calendar dateAndTime = Calendar.getInstance();
		Date startTime = dateAndTime.getTime();

		// Read Parameter File
		System.out.println("\nParameter File Name is: " + args[0] + "\n");
		Parameters parmValues = new Parameters(args[0]);

		// Write Parameters To Summary Output File
		String summaryFileName = Parameters.expID + "_summary.txt";
		FileWriter summaryOutput = new FileWriter(summaryFileName);
		parmValues.outputParameters(summaryOutput);

		// Set up Fitness Statistics matrix
		fitnessStats = new double[4][Parameters.generations];
		for (int i = 0; i < Parameters.generations; i++) {
			for (int j = 0; j < 4; j++) {
				fitnessStats[j][i] = 0;
			}
		}

		// Problem Specific Setup - For new new fitness function problems,
		// create
		// the appropriate class file (extending FitnessFunction.java) and add
		// an else_if block below to instantiate the problem.
		FitnessFunction problem = null;

		if (Parameters.problemType.equals("NM")) {
			problem = new NumberMatch();
		} else if (Parameters.problemType.equals("CFB")) {
			problem = new CurveFitBinary();
		} else if (Parameters.problemType.equals("CFG")) {
			problem = new CurveFitGray();
		} else if (Parameters.problemType.equals("CFF")) {
			problem = new CurveFitFloat();
		} else if (Parameters.problemType.equals("CFO")) {
			problem = new CurveFitOther();
		} else if (Parameters.problemType.equals("OM")) {
			problem = new OneMax();
		} else
			System.out.println("Invalid Problem Type");

		System.out.println(problem.name);

		// Initialize RNG, array sizes and other objects
		// Initialize objects
		Chromo chromo = null;
		Chromo[] member = null;
		Chromo[] child = null;
		Chromo bestOfGenChromo = null;
		Chromo bestOfRunChromo = null;
		Chromo bestOverAllChromo = null;
		// done Initialize

		r.setSeed(Parameters.seed);
		memberIndex = new int[Parameters.popSize];
		memberFitness = new double[Parameters.popSize];

		switch (Parameters.representation) {
		// binary
		case 1: {
			chromo = new ChromoBinary();
			member = new ChromoBinary[Parameters.popSize];
			child = new ChromoBinary[Parameters.popSize];
			bestOfGenChromo = new ChromoBinary();
			bestOfRunChromo = new ChromoBinary();
			bestOverAllChromo = new ChromoBinary();
			break;
		}
			// Gray
		case 2: {
			chromo = new ChromoGray();
			member = new ChromoGray[Parameters.popSize];
			child = new ChromoGray[Parameters.popSize];
			bestOfGenChromo = new ChromoGray();
			bestOfRunChromo = new ChromoGray();
			bestOverAllChromo = new ChromoGray();
			break;
		}
			// Floating point
		case 3: {
			chromo = new ChromoFloat();
			member = new ChromoFloat[Parameters.popSize];
			child = new ChromoFloat[Parameters.popSize];
			bestOfGenChromo = new ChromoFloat();
			bestOfRunChromo = new ChromoFloat();
			bestOverAllChromo = new ChromoFloat();
			break;
		}
			// Other representation
		case 4: {
			chromo = new Chromo();
			member = new Chromo[Parameters.popSize];
			child = new Chromo[Parameters.popSize];
			bestOfGenChromo = new Chromo();
			bestOfRunChromo = new Chromo();
			bestOverAllChromo = new Chromo();
			break;
		}
		}

		if (Parameters.minORmax.equals("max")) {
			defaultBest = 0;
			defaultWorst = 999999999999999999999.0;
		} else {
			defaultBest = 999999999999999999999.0;
			defaultWorst = 0;
		}

		bestOverAllChromo.rawFitness = defaultBest;
		brfStdStorage = new double[Parameters.numRuns + 1];

		sumOptimumGen = 0;
		optimumGeneration = new int[Parameters.numRuns];

		// Start program for multiple runs
		for (R = 1; R <= Parameters.numRuns; R++) {

			bestOfRunChromo.rawFitness = defaultBest;

			// Initialize First Generation
			for (int i = 0; i < Parameters.popSize; i++) {
				switch (Parameters.representation) {
				// binary
				case 1: {
					member[i] = new ChromoBinary();
					child[i] = new ChromoBinary();
					break;
				}
					// Gray
				case 2: {
					member[i] = new ChromoGray();
					child[i] = new ChromoGray();
					break;
				}
					// Floating point
				case 3: {
					member[i] = new ChromoFloat();
					child[i] = new ChromoFloat();
					break;
				}
					// Other representation
				case 4: {
					member[i] = new Chromo();
					child[i] = new Chromo();
					break;
				}
				}
			}

			// Initialize our max optimum value for the run
			optimumGeneration[R - 1] = 0;

			// Begin Each Run
			for (G = 0; G < Parameters.generations; G++) {

				sumProFitness = 0;
				sumSclFitness = 0;
				sumRawFitness = 0;
				sumRawFitness2 = 0;
				bestOfGenChromo.rawFitness = defaultBest;

				// Test Fitness of Each Member
				for (int i = 0; i < Parameters.popSize; i++) {

					member[i].rawFitness = 0;
					member[i].sclFitness = 0;
					member[i].proFitness = 0;

					problem.doRawFitness(member[i]);
					sumRawFitness = sumRawFitness + member[i].rawFitness;
					sumRawFitness2 = sumRawFitness2 + member[i].rawFitness
							* member[i].rawFitness;

					if (Parameters.minORmax.equals("max")) {
						if (member[i].rawFitness > bestOfGenChromo.rawFitness) {
							chromo.copyB2A(bestOfGenChromo, member[i]);
							bestOfGenR = R;
							bestOfGenG = G;
						}
						if (member[i].rawFitness > bestOfRunChromo.rawFitness) {
							chromo.copyB2A(bestOfRunChromo, member[i]);
							bestOfRunR = R;
							bestOfRunG = G;
						}
						if (member[i].rawFitness > bestOverAllChromo.rawFitness) {
							chromo.copyB2A(bestOverAllChromo, member[i]);
							bestOverAllR = R;
							bestOverAllG = G;
						}
					} else {
						if (member[i].rawFitness < bestOfGenChromo.rawFitness) {
							chromo.copyB2A(bestOfGenChromo, member[i]);
							bestOfGenR = R;
							bestOfGenG = G;
						}
						if (member[i].rawFitness < bestOfRunChromo.rawFitness) {
							chromo.copyB2A(bestOfRunChromo, member[i]);
							bestOfRunR = R;
							bestOfRunG = G;
						}
						if (member[i].rawFitness < bestOverAllChromo.rawFitness) {
							chromo.copyB2A(bestOverAllChromo, member[i]);
							bestOverAllR = R;
							bestOverAllG = G;
						}
					}
				}

				// Accumulate fitness statistics
				fitnessStats[0][G] += sumRawFitness / Parameters.popSize;
				fitnessStats[1][G] += bestOfGenChromo.rawFitness;

				// Accumulate the squared sum for sample std
				// Position [2] is for the average raw fitness squared
				// Position [3] is for the best of generation fitness squared
				fitnessStats[2][G] += (sumRawFitness / Parameters.popSize)
						* (sumRawFitness / Parameters.popSize);
				fitnessStats[3][G] += bestOfGenChromo.rawFitness
						* bestOfGenChromo.rawFitness;

				averageRawFitness = sumRawFitness / Parameters.popSize;
				stdevRawFitness = Math.sqrt(Math.abs(sumRawFitness2
						- sumRawFitness * sumRawFitness / Parameters.popSize)
						/ (Parameters.popSize - 1));

				// Output generation statistics to screen
				// System.out.println(R + "\t" + G + "\t" +
				// (int)bestOfGenChromo.rawFitness + "\t" + averageRawFitness +
				// "\t" + stdevRawFitness);

				// Output generation statistics to summary file
				summaryOutput.write(" R ");
				Hwrite.right(R, 3, summaryOutput);
				summaryOutput.write(" G ");
				Hwrite.right(G, 3, summaryOutput);
				Hwrite.right((int) bestOfGenChromo.rawFitness, 30,
						summaryOutput);
				Hwrite.right(averageRawFitness, 30, 5, summaryOutput);
				Hwrite.right(stdevRawFitness, 30, 5, summaryOutput);
				summaryOutput.write("\n");

				// *********************************************************************
				// **************** SCALE FITNESS OF EACH MEMBER AND SUM
				// ***************
				// *********************************************************************

				switch (Parameters.scaleType) {

				case 0: // No change to raw fitness
					for (int i = 0; i < Parameters.popSize; i++) {
						member[i].sclFitness = member[i].rawFitness + .000001;
						sumSclFitness += member[i].sclFitness;
					}
					break;

				case 1: // Fitness not scaled. Only inverted.
					for (int i = 0; i < Parameters.popSize; i++) {
						member[i].sclFitness = 1 / (member[i].rawFitness + .000001);
						sumSclFitness += member[i].sclFitness;
					}
					break;

				case 2: // Fitness scaled by Rank (Maximizing fitness)

					// Copy genetic data to temp array
					for (int i = 0; i < Parameters.popSize; i++) {
						memberIndex[i] = i;
						memberFitness[i] = member[i].rawFitness;
					}
					// Bubble Sort the array by floating point number
					for (int i = Parameters.popSize - 1; i > 0; i--) {
						for (int j = 0; j < i; j++) {
							if (memberFitness[j] > memberFitness[j + 1]) {
								TmemberIndex = memberIndex[j];
								TmemberFitness = memberFitness[j];
								memberIndex[j] = memberIndex[j + 1];
								memberFitness[j] = memberFitness[j + 1];
								memberIndex[j + 1] = TmemberIndex;
								memberFitness[j + 1] = TmemberFitness;
							}
						}
					}
					// Copy ordered array to scale fitness fields
					for (int i = 0; i < Parameters.popSize; i++) {
						member[memberIndex[i]].sclFitness = i;
						sumSclFitness += member[memberIndex[i]].sclFitness;
					}

					break;

				case 3: // Fitness scaled by Rank (minimizing fitness)

					// Copy genetic data to temp array
					for (int i = 0; i < Parameters.popSize; i++) {
						memberIndex[i] = i;
						memberFitness[i] = member[i].rawFitness;
					}
					// Bubble Sort the array by floating point number
					for (int i = 1; i < Parameters.popSize; i++) {
						for (int j = (Parameters.popSize - 1); j >= i; j--) {
							if (memberFitness[j - i] < memberFitness[j]) {
								TmemberIndex = memberIndex[j - 1];
								TmemberFitness = memberFitness[j - 1];
								memberIndex[j - 1] = memberIndex[j];
								memberFitness[j - 1] = memberFitness[j];
								memberIndex[j] = TmemberIndex;
								memberFitness[j] = TmemberFitness;
							}
						}
					}
					// Copy array order to scale fitness fields
					for (int i = 0; i < Parameters.popSize; i++) {
						member[memberIndex[i]].sclFitness = i;
						sumSclFitness += member[memberIndex[i]].sclFitness;
					}

					break;

				default:
					System.out.println("ERROR - No scaling method selected");
				}

				// *********************************************************************
				// ****** PROPORTIONALIZE SCALED FITNESS FOR EACH MEMBER AND SUM
				// *******
				// *********************************************************************

				for (int i = 0; i < Parameters.popSize; i++) {
					member[i].proFitness = member[i].sclFitness / sumSclFitness;
					sumProFitness = sumProFitness + member[i].proFitness;
				}

				// *********************************************************************
				// ************ CROSSOVER AND CREATE NEXT GENERATION
				// *******************
				// *********************************************************************

				int parent1 = -1;
				int parent2 = -1;

				// Assumes always two offspring per mating
				for (int i = 0; i < Parameters.popSize; i = i + 2) {

					// Select Two Parents
					parent1 = chromo.selectParent(member);
					parent2 = parent1;
					while (parent2 == parent1) {
						parent2 = chromo.selectParent(member);
					}

					// Crossover Two Parents to Create Two Children
					randnum = r.nextDouble();
					if (randnum < Parameters.xoverRate) {
						chromo.mateParents(parent1, parent2, member[parent1],
								member[parent2], child[i], child[i + 1]);
					} else {
						chromo.mateParents(parent1, member[parent1], child[i]);
						chromo.mateParents(parent2, member[parent2],
								child[i + 1]);
					}
				} // End Crossover

				// Mutate Children
				for (int i = 0; i < Parameters.popSize; i++) {
					child[i].doMutation();
				}

				// Swap Children with Last Generation
				for (int i = 0; i < Parameters.popSize; i++) {
					chromo.copyB2A(member[i], child[i]);
				}

			} // Repeat the above loop for each generation

			// Store the generation that the best individual was found, just
			// because
			optimumGeneration[R - 1] = bestOfRunG;

			// Add the current optimumGeneration to the sum and sum squared for
			// the std calculation
			sumOptimumGen += bestOfRunG;
			sumOptimumGenSqr += bestOfRunG * bestOfRunG;

			summaryOutput.write("R    G             RawFitness\n");

			Hwrite.left(bestOfRunR, 4, summaryOutput);
			Hwrite.right(bestOfRunG, 4, summaryOutput);
			problem.doPrintGenes(bestOfRunChromo, summaryOutput);

			averageBestRunFitness += bestOfRunChromo.rawFitness;
			brfStdStorage[R] = bestOfRunChromo.rawFitness;

			// System.out.println(R + "\t" + "B" + "\t"+
			// (int)bestOfRunChromo.rawFitness);

		} // End of a Run

		Hwrite.left("B", 8, summaryOutput);

		problem.doPrintGenes(bestOverAllChromo, summaryOutput);

		double avgAvgFitStd, avgBestFitStd;

		// Output Fitness Statistics matrix
		summaryOutput.write("Gen    AvgAvgFit  Stdev     AvgBestFit Stdev\n");
		for (int i = 0; i < Parameters.generations; i++) {

			avgAvgFitStd = Math.sqrt(Math.abs(fitnessStats[2][i]
					- // sum of average fitness squared
					fitnessStats[0][i] * fitnessStats[0][i]
					/ Parameters.numRuns)
					/ (Parameters.numRuns - 1));

			avgBestFitStd = Math.sqrt(Math.abs(fitnessStats[3][i]
					- // sum of best generation fitness squared
					fitnessStats[1][i] * fitnessStats[1][i]
					/ Parameters.numRuns)
					/ (Parameters.numRuns - 1));

			Hwrite.left(i, 7, summaryOutput);
			Hwrite.left(fitnessStats[0][i] / Parameters.numRuns, 30, 2,
					summaryOutput);
			Hwrite.left(avgAvgFitStd, 30, 2, summaryOutput);
			Hwrite.left(fitnessStats[1][i] / Parameters.numRuns, 30, 2,
					summaryOutput);
			Hwrite.left(avgBestFitStd, 30, 2, summaryOutput);
			summaryOutput.write("\n");
		}

		// Average Best Run Fitness Standard Deviation calculation and CI
		averageBestRunFitness = averageBestRunFitness / Parameters.numRuns;
		for (R = 1; R <= Parameters.numRuns; R++) {
			averageBestRunFitnessStd += Math.pow(brfStdStorage[R]
					- averageBestRunFitness, 2);
		}
		averageBestRunFitnessStd = Math.sqrt(averageBestRunFitnessStd
				/ (Parameters.numRuns - 1));

		averageBestRunFitnessCi = averageBestRunFitnessStd * 1.96;

		// Optimum Generation Standard Deviation calculation and CI
		averageOptimumGenStd = Math.sqrt(Math.abs(sumOptimumGenSqr
				- sumOptimumGen * sumOptimumGen / Parameters.numRuns)
				/ (Parameters.numRuns - 1));

		averageOptimumGenCi = averageOptimumGenStd * 1.96;

		// Homework output
		summaryOutput.write("\nPart B)\n");

		summaryOutput
				.write("Average Best Run Fitness      Standard Deviation       CI\n");
		Hwrite.left(averageBestRunFitness, 30, 2, summaryOutput);
		Hwrite.left(averageBestRunFitnessStd, 25, 2, summaryOutput);
		summaryOutput.write("[");
		Hwrite.left((averageBestRunFitness - averageBestRunFitnessCi), 30, 2,
				summaryOutput);
		summaryOutput.write(", ");
		Hwrite.right((averageBestRunFitness + averageBestRunFitnessCi), 30, 2,
				summaryOutput);
		summaryOutput.write("]");

		summaryOutput.write("\n\nPart C)\n");

		double averageOptimumOfGen = (double) sumOptimumGen
				/ Parameters.numRuns;

		summaryOutput
				.write("Average Generation Optimum Found     Standard Deviation   CI\n");
		Hwrite.left(averageOptimumOfGen, 37, 2, summaryOutput);
		Hwrite.left(averageOptimumGenStd, 20, 2, summaryOutput);
		summaryOutput.write("[");
		Hwrite.left((averageOptimumOfGen - averageOptimumGenStd), 8, 2,
				summaryOutput);
		summaryOutput.write(", ");
		Hwrite.right((averageOptimumOfGen + averageOptimumGenStd), 8, 2,
				summaryOutput);
		summaryOutput.write("]\n");

		// Simply because I think it is interesting, I am going to print out the
		// optimum's and the
		// generation they were found
		summaryOutput
				.write("\nList of top fitness per run and generation it was found:");
		summaryOutput.write("\nRun\t\tGen\t\tBest Fitness\n");
		for (int i = 0; i < Parameters.numRuns; i++) {
			summaryOutput.write((i + 1) + "\t\t" + optimumGeneration[i]
					+ "\t\t" + brfStdStorage[i + 1] + "\n");
		}

		System.out.println();
		System.out.println("Start:  " + startTime);
		dateAndTime = Calendar.getInstance();
		Date endTime = dateAndTime.getTime();
		System.out.println("End  :  " + endTime);

		summaryOutput.write("\nStart:  " + startTime);
		summaryOutput.write("\nEnd  :  " + endTime);

		summaryOutput.write("\n");
		summaryOutput.close();

	} // End of Main Class

} // End of Search.Java ******************************************************

